package 不同路径;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.uniquePaths(5,4));
    }

    public int uniquePaths(int m, int n) {
        int[][] ints = new int[m][n];
        for (int i = 0; i < m; i++) {
            ints[i][n-1] = 1;
        }
        for (int i = 0; i < n; i++) {
            ints[m-1][i] = 1;
        }
        int sum = uniquePaths(m,n,0,0,0);
        return sum;
    }

    public int uniquePaths(int m, int n,int y,int x,int sum) {

        int count = sum;
        if(x == (n-1) && y == (m-1)){
            ++sum;
            return sum;
        }

        //先向右
        if(x != n -1){
            count = uniquePaths(m,n,y,x+1,count);
        }

        //再向下
        if(y != m -1){
            count = uniquePaths(m,n,y+1,x,count);
        }

        return count;
    }
}
